package 实现数据结构.算法.排序;

/**
 * @Title 排序汇总 十大经典排序算法
 * @Author zhengqiang.tan
 * @Date 2021/3/1 4:24 PM
 * https://www.runoob.com/w3cnote/selection-sort.html
 */
public class 排序算法汇总 {
    public static void main(String[] args) {
        int arr[] = {3, 4, 1, 5, 6, 3, 8, 2, 7};
        printArr(arr);
//        selectSort(arr);
//        bubbleSort(arr);
//        insertSort(arr);

        printArr(quickSort(arr,0,arr.length-1));

//        printArr(arr);

    }


    /**
     * 选择排序 [ 4,3,5,1]
     * 4 3 5 1 len=4
     * i 0 1 2
     * j   1 2 3
     */
    public static void selectSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        int N = arr.length;
        // 总共需要N-1次比较
        for (int i = 0; i < N - 1; i++) {
            int minIndex = i;
            // 每轮需要比较N-i次
            for (int j = i + 1; j < N; j++) {
                minIndex = arr[j] < arr[minIndex] ? j : minIndex;

            }
            // 将找到的最小值和i位置的值进行交换
            swap(arr, i, minIndex);
        }
    }

    /**
     * 冒泡排序(相邻元素比较，左边大于右边就交换，然后循环)
     */
    public static void bubbleSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        int N = arr.length;
        // 写法1：
        for (int i = 0; i < N - 1; i++) {
            for (int j = i + 1; j < N; j++) {
                if (arr[i] > arr[j]) {
                    swap(arr, i, j);
                }
            }
        }
        // 写法2：
//        for (int end = N - 1; end >= 0; end--) {
//            for (int second = 1; second <= end; second++) {
//                if (arr[second - 1] > arr[second]) {
//                    swap(arr, second - 1, second);
//                }
//            }
//        }
    }


    /**
     * 插入排序
     *
     * @param arr
     */
    public static void insertSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        int N = arr.length;
        for (int i = 1; i < N; i++) {
            int index = i;
            while (index - 1 >= 0 && arr[index - 1] > arr[index]) {
                swap(arr, index - 1, index);
                index--;
            }
        }
    }


    /**
     * 快速排序
     */
    public static int[] quickSort(int[] arr, int left, int right) {
        if (left < right) {
            int partitionIndex = partition(arr, left, right);
            quickSort(arr, left, partitionIndex - 1);
            quickSort(arr, partitionIndex + 1, right);
        }
        return arr;
    }

    private static int partition(int[] arr, int left, int right) {
        // 设定基准值（pivot）
        int pivot = left;
        int index = pivot + 1;
        for (int i = index; i <= right; i++) {
            if (arr[i] < arr[pivot]) {
                swap(arr, i, index);
                index++;
            }
        }
        swap(arr, pivot, index - 1);
        return index - 1;
    }




    /**
     * 交换两个位置的元素
     *
     * @param arr
     * @param i
     * @param j
     */
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
    }

    /**
     * 打印数组
     *
     * @param arr
     */
    public static void printArr(int[] arr) {
        int N = arr.length;
        for (int i = 0; i < N; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    /**
     * ^是异或运算符，异或的规则是转换成二进制比较，相同为0，不同为1
     */
    public static void swap2(int[] arr, int i, int j) {
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
    }

}
